
/**
 * @file	flow_network.cpp
 * @author  Alessandro Carrega <contact@alexcarrega.com>
 * @version 2.0
 * 
 * @secion LICENSE
 *
 * This file is part of graph_max_flow.
 *
 * graph_max_flow is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * graph_max_flow is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with graph_max_flow.  If not, see <http://www.gnu.org/licenses/>.
 * 
 */
 
#include <cstring>

#include "flow_network.h"

#define NO_PRECEDENT 0

FlowNetwork::FlowNetwork(int num_node, int num_edge):  q_(num_node), num_node_(num_node), num_edge_(num_edge)
{
	precedent_ = new int[num_node + 1]; // alloca un elemento in più dato i nodi partono da 1
	capacity_ = new int*[num_node + 1]; // alloca un elemento in più dato i nodi partono da 1
	flow_ =  new int*[num_node + 1]; // alloca un elemento in più dato i nodi partono da 1
	
	/*
	 * flow_ e capacity_ sono due matrici di dimensione: (num_node + 1 ) x (num_node + 1).
	 * Questo ciclo è necessario per allocare le matrici.
	 */
	for (int i = 1; i <= num_node; i++)
	{
		capacity_[i] = new int[num_node + 1];
		/*
		 * Inizializza a zero il contenuto in capacity_[i].
		 * Il + 1 è perchè la prima posizione è dummy.
		 */
		memset(capacity_[i] + 1, 0, sizeof(int) * num_node); 
		
		flow_[i] = new int[num_node + 1];
		/*
		 * Inizializza a zero il contenuto in capacity_[i].
		 * Il + 1 è perchè la prima posizione è dummy.
		 */ 
		memset(flow_[i] + 1, 0, sizeof(int) * num_node);
	}
}

 void FlowNetwork::add_edge(int u, int v, int cap)
{
	capacity_[u][v] = cap;
}

bool FlowNetwork::has_path(int source, int sink)
{
	// Inizializzo la coda.
	q_.reset();	
	// Inserisco il nodo sorgente source.
	q_.enqueue(source);
	// Il nodo sorgente source non è ha predecessore nel percorso da source a sink.
	precedent_[source] = NO_PRECEDENT;
	
	int u;
	while (!q_.empty())
	{
		// Estraggo un nodo dalla coda e lo visito.
		u = q_.dequeue();
		
		// Inserisco in coda tutti i nodi adicenti a u ancora da visitare con residuo (capacity - flow) > 0.
		for (int v = 1; v <= num_node_; v++)
		{
			if (q_.is_to_visit(v) && capacity_[u][v] - flow_[u][v] > 0)
			{
				// Inserisco il nodo v collegato a u in code e imposto come predecessore di v proprio u.
				q_.enqueue(v);				
				precedent_[v] = u;
			}
		}
	}
	// Il percorso esiste se il nodo sink è stato visitato.
	return q_.is_visited(sink);
}

int FlowNetwork::max_flow(int source, int sink)
{
	int u, v, residual, min_residual, result = 0;
	// fino a quando esiste un percorso tra source e sink
	while (has_path(source, sink))
	{
		/*
		 * il percorso esiste ed è in precedent_.
		 * Percorro precedent_ a partire dal
		 * sink fino allo sorgente e trovo il residuo minimo
		 * nel percorso trovato.
		 */
		u = sink;
		v =  precedent_[u];
		min_residual = capacity_[v][u] - flow_[v][u];
		
		for (u = v, v = precedent_[u]; v != NO_PRECEDENT; u = v, v = precedent_[u])
		{
			residual = capacity_[v][u] - flow_[v][u];
			if (min_residual > residual)
			{
				min_residual = residual;
			}
		}
		
		// Aggiorno i nuovo flussi degli edge del percorso trovato.
		for (u = sink, v = precedent_[u]; v != NO_PRECEDENT; u = v, v = precedent_[u])
		{
			flow_[v][u] += min_residual;
			flow_[u][v] -= min_residual;
		}
		// Aggiungo il residuo minimo al risultato finale.
		result += min_residual;
	}
	/*
	 * Il risultato è la somma di tutti i residui minimi fino a quando è esistito
	 * un percorso con residuo > 0 tra source e sink.
	 */
	return result;
}
